package JZOffer;

/**
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I
 * 统计一个数字在排序数组中出现的次数。
 *
 * 示例 1:
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 *
 * 示例 2:
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 * */


class Solution53_1_1 {
    public int search(int[] nums, int target) {
        if (nums.length == 0) return 0;
        int firstPosition = findFirstPosition(nums, target);
        int lastPositiom = findLastPosition(nums, target);
        if (nums[firstPosition] != target) {
            return 0;
        }
        return lastPositiom - firstPosition;

    }

    public int findFirstPosition(int[] nums, int k) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == k) {
                if (nums[mid] - 1 == k){
                    if (mid - 1 >= 0 && nums[mid - 1] == k) {
                        r = mid - 1;
                    }else {
                        return mid;
                    }
                }
            }else if (nums[mid] > k) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return l;
    }

    public int findLastPosition(int[] nums, int k) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == k) {
                if (nums[mid] - 1 == k){
                    if (mid + 1 < nums.length && nums[mid + 1] == k) {
                        r = mid + 1;
                    }else {
                        return mid;
                    }
                }
            }else if (nums[mid] > k) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return l;
    }
}

//进一步，我们可以直接经过两次「二分」找到左右边界，计算总长度即是 target的数量。
class Solution53_1_2 {
    public int search(int[] nums, int target) {
        if (nums.length == 0) return 0;

        int a = -1, b = -1;

        //二分出左边界
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[r] != target) return 0;
        a = r;

        //二分出有边界
        l = 0; r = nums.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        if (nums[r] != target) return 0;
        b = r;

        return b - a + 1;

    }
}